// @coding: utf8

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <random>
#include <cassert>

std::string f(const std::vector<int>& input)
{
    if (input.empty())
        return "";
    std::string result;
    std::size_t cnt = input.size();
    // 函数参数为const类型，假定题目限制不允许修改源数据
    for (std::size_t idx = 0; idx < cnt; ++idx)
    {
        // 题目给定了数字到字符，直接+48完成转换
        result.push_back(input[idx] + 48);
    }
    // 完成排序
    std::sort(result.begin(), result.end());
    std::size_t charater_cnt = result.size();
    // 插入空格: 假定要求不使用额外空间, 需要的空格数量=字符数-1
    result.resize(result.size() + result.size() - 1, ' ');
    // 第n个字符在调整后应在n*2的位置
    /*
    1,2,3,4,5
    1,0,2,0,3
    */
   // 双指针，left起点为最后一个有效字符串，right为最后一个字符
   int left = charater_cnt - 1;
   int right = result.size() - 1;
   while (left > 0)
   {
        std::swap(result[left], result[left * 2]);
        --left;
   }

    return result;
}

// 空数据测试
bool testcase_01()
{
    std::vector<int> input{};
    auto result = f(input);
    return result.size() == 0;
}

// 一个数字测试边界
bool testcase_02()
{
    std::vector<int> input{1};
    auto result = f(input);
    return result.compare("1") == 0;
}

// 随机数据用例
bool testcase_03()
{
    srand(time(nullptr));
    std::size_t cnt = rand() % 100;
    std::vector<int> input;
    for (auto idx = cnt; idx > 0; --idx)
    {
        input.push_back(idx);
    }
    auto result = f(input);
    // 还原成int vector
    std::vector<int> verify;
    for (auto idx = 0; idx < result.size(); ++idx)
    {
        if (idx % 2 == 0)
            verify.push_back(result[idx] - 48);
    }
    return std::equal(input.begin(), input.end(), verify.rbegin(), verify.rend());
}


int main()
{
    assert(testcase_01());
    assert(testcase_02());
    assert(testcase_03());

    return 0;
}